/**
 * 给定数组和L，如果两个元素差的绝对值不超过L就能交换
 * 要求使得数组字典序最小
 * 如果a、b可交换，b、c可交换，则a/b/c三者可以形成任意排列
 * 因此对数组元素做一个分组，然后每组单独排序即可
 * 实现时可以先排序，再O(N)分组
 */
class Solution {

public:
    vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) {        
        int n = nums.size();
        vector<int> ans(n);
        vector<int> zhibiao(n);
        for(int i=0;i<n;++i) zhibiao[i] = i;
        sort(zhibiao.begin(), zhibiao.end(), [&](int a, int b){return nums[a] < nums[b];});
        int k = 0;
        while(1){
            int t = 1;
            set<int> ss;
            ss.insert(zhibiao[k]);
            while(k + t < n and nums[zhibiao[k + t]] - nums[zhibiao[k + t - 1]] <= limit){
                ss.insert(zhibiao[k + t]);
                ++t;
            }

            for(auto i : ss){
                ans[i] = nums[zhibiao[k]];
                ++k;            
            }
            
            if(k == n) break;
        }      
        return ans;  
    }
    
};